package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _0015 {
    /**
     * 三数之和
     */
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> ans = new ArrayList<>();
            int n = nums.length;
            for(int i=0;i<n-2;i++){
                int x= nums[i];
                if(i>0&&x==nums[i-1]){
                    continue;
                }
                if(x+nums[n-1]+nums[n-2]<0){
                    continue;
                }
                if(x+nums[i+1]+nums[i+2]>0){
                    break;
                }
                int j=i+1;
                int k = n-1;
                while(j<k){
                    int sum = x+nums[j]+nums[k];
                    if (sum>0){
                        k--;
                    }else if(sum<0){
                        j++;
                    }else{
                        List<Integer> list = new ArrayList<>();
                        list.add(x);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        ans.add(list);
                        j+=1;
                        while(j<k&&nums[j]==nums[j-1]){
                            j++;
                        }
                        k-=1;
                        while(k>j&&nums[k]==nums[k+1]){
                            k--;
                        }
                    }
                }

            }
            return ans;
        }
    }
}
